1. Technical Field
The present invention relates generally to a method of performing a multiplication operation in a binary extension finite field and, more particularly, to a method that produces a polynomial by expanding polynomial basis multiplication for the multiplication of two polynomials in a binary extension finite field GF(2m) and performs a multiplication operation in a binary extension finite field using a mapping table in which bit values having pieces of information about respective terms of the produced polynomial are mapped to respective rows.
2. Description of the Related Art
An Elliptic Curve Cryptosystem (ECC) was proposed by Neal Kobliz and Victor Millerin in 1985 and since then, a lot of research into ECC has been conducted as a public key cryptosystem. This cryptosystem is based on the difficulty of discrete logarithm of points on an elliptic curve, and is advantageous in that it is processed faster and has a smaller key than the Rivest-Shamir-Adleman (RSA) algorithm/Digital Signature Algorithm (DSA) which are widely utilized as a conventional public key cryptosystem when a comparison is performed at the same security level. For example, it is well known that the security of ECC having a key size of about 160 bits is identical to that of RSA having a key size of 1024 bits. Therefore, ECC has attracted attention as a public key cryptosystem suitable for smart cards or the like having limited computing ability and memory.
Operations in such ECC include operations of points on an elliptic curve, which include the addition of two different points, a one-point doubling operation, etc. Such operations of points on the elliptic curve include combinations of finite field addition, finite field subtraction, finite field multiplication, finite field division, etc.
A finite field denotes a field having a finite number of elements for which addition, subtraction, multiplication, and division are defined, and has only one field having pm elements with respect to a prime number p and a positive integer m. This field is called a Galois field and is represented by GF(pm). Generally, operations, such as addition, subtraction, multiplication, and division, in a finite field are implemented using hardware and are then calculated. When addition and subtraction operations in the finite field GF(pm) are performed using hardware, the implementation of the operations is simplified. However, there is a problem in that the implementation of multiplication and division operations using hardware is complicated. In order to implement fast elliptic curve cryptography, it is essential that finite field multiplication, in particular, is processed at high speed. A multiplier for performing multiplication in the finite field GF(pm) implemented using hardware is disclosed in Korean Patent Application Publication No. 2001-0068349 or the like.
A conventional finite field GF(pm) multiplication algorithm disclosed in Korean Patent Application Publication No. 2001-0068349 or the like is generally implemented using an algorithm represented in the following Table 1.
TABLE 1Conventional algorithm method for polynomial multiplicationINPUT: Binary polynomials a(z) and b(z) of degree at most m−1OUTPUT: c(z) = a(z) · b(z)1. C ←02. For k from 1 to W−1 do2.1 For j from 0 to t−1If the kth bit of A[j] is 1 then C{j} ←C{j}+B2.2 If k ≠ W−1 then B ← B·z3. Return (C)